﻿#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
//1.最小栈;
//class MinStack {
//public:
//    MinStack()
//    {
//    }
//
//    void push(int val)
//    {
//        _pushst.push(val);
//        if (_minst.empty())
//        {
//            _minst.push(val);
//        }
//        else
//        {
//            if (val <= _minst.top())
//            {
//                _minst.push(val);
//            }
//        }
//    }
//
//    void pop()
//    {
//        if (_pushst.top() == _minst.top())
//        {
//            if (!_minst.empty())
//                _minst.pop();
//        }
//        _pushst.pop();
//    }
//
//    int top()
//    {
//        return _pushst.top();
//    }
//
//    int getMin()
//    {
//        return _minst.top();
//    }
//private:
//    stack<int> _pushst;
//    stack<int> _minst;
//};

//2.栈的弹出压入序列
//class Solution {
//public:

//    bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
//    {
//        stack<int> st;
//        int i = 0, j = 0;
//        int size = pushV.size();
//        while (i < size)
//        {
//            st.push(pushV[i]);
//            if (st.top() == popV[j])
//            {
//                while (!st.empty() && st.top() == popV[j])
//                {
//                    st.pop();
//                    j++;
//                }
//            }
//            i++;
//        }
//        return st.empty();
//    }
//};

//优化版本；
//class Solution {
//public:

//    bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
//    {
//        int index = 0;
//        stack<int>st;
//        for (auto& e : pushV)
//        {
//            st.push(e);
//            while (!st.empty() && st.top() == popV[index])
//            {
//                st.pop();
//                index++;
//            }
//        }
//        return st.empty();
//    }
//};

//3.二叉树的层序遍历;
//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root)
//    {
//        queue<TreeNode*> q;
//        vector<vector<int>> vv;
//        int size = 0;
//        if (root)
//        {
//            q.push(root);
//        }
//        while (!q.empty())
//        {
//            size = q.size();
//            vector<int> v;
//            while (size > 0)
//            {
//                v.push_back((q.front())->val);
//                if (q.front()->left)
//                {
//                    q.push(q.front()->left);
//                }
//                if (q.front()->right)
//                {
//                    q.push(q.front()->right);
//                }
//                q.pop();
//                size--;
//            }
//            vv.push_back(v);
//        }
//        return vv;
//    }
//};
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        vector<int> ret;
        sort(nums.begin(), nums.end());
        int i = 0;
        for (; i < nums.size() - 1; )
        {
            if (nums[i] == nums[i + 1])
                i += 2;
            else
            {
                ret.push_back(nums[i]);
                i++;
            }
        }
        if (i < nums.size())
            ret.push_back(nums[i]);
        return ret;
    }
};
int main()
{   
    vector<int> v{1, 2, 1, 3, 2, 5};
    Solution s;
    s.singleNumber(v);
    return 0;
}
